package DFS递归搜索与回溯.数独;

/**
 * @Date 2024/9/15 21:16
 * @description: 有效的数独
 * .https://leetcode.cn/problems/valid-sudoku/description/
 * @Author LittleNight
 */
public class likou36 {

    /**
     * 判断是否为有效的数独. 练习
     * @param board
     * @return
     */
    boolean[][] row, col;
    boolean[][][] grid;
    int m, n;
    public boolean isValidSudoku(char[][] board) {
        m = board.length; n = board[0].length;
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10]; // 一共有10个数

        // 遍历数组
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 是数字
                if(board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    // todo 注意为 true 才表示出现过
                    // if(!row[i][num] || !col[j][num] || !grid[i / 3][j / 3][num]) {
                    if(row[i][num] || col[j][num] || grid[i / 3][j / 3][num]) {
                        // 出现任何一个重复的, 直接返回 false
                        return false;
                    }
                    // 否则标记出现过
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        }
        return true;
    }



//    boolean row[][];
//    boolean col[][];
//    boolean grid[][][];
//    public boolean isValidSudoku(char[][] board) {
//        // 题目说是九行九列. 多开一个空间就不用映射了
//        row = new boolean[9][10];
//        col = new boolean[9][10];
//        grid = new boolean[3][3][10];
//
//        // 遍历原数组
//        for (int i = 0; i < 9; i++) {
//            for (int j = 0; j < 9; j++) {
//                if(board[i][j] != '.') {
//                    int num = board[i][j] - '0';
//                    // 为 true 表示出现过
//                    if(row[i][num] || col[j][num] || grid[i / 3][j / 3][num]) {
//                        return false;
//                    }
//                    // 标记已经出现过
//                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
//                }
//            }
//        }
//        // 遍历完都没有返回 false, 说明是一个合格的数独
//        return true;
//    }

}
